# -*- coding: utf-8 -*-
from collections import deque
from model.person import Person
from model.solution import Solution


class Backtracking:

    def __init__(self, filename):
        self.men = deque()
        self.women = []
        self.solution = None
        self.__temp = Solution()
        self.load_data(filename)

    def load_data(self, filename):
        """Loads men and women [O(n)] and their preference lists [O(n)]
        O(n^2)"""
        file = open(filename)
        genre = 'Male'
        for line in file:
            words = line.split(":")
            if line == '\n':
                genre = 'Female'
            else:
                name = words[0]
                preferences = words[1]
                person = Person(name, preferences)
                if genre == 'Male':
                    self.men.append(person)
                else:
                    self.women.append(person)

        file.close()

    def match(self):
        """Finds all stable matchings
        O(n^n)"""
        # If there are still
        if len(self.men) != 0:
            #Take the first man in the list
            m = self.men.pop()
            #Check for women without commitment
            for w in self.women:
                if w.fiancee is None:
                    #Build pair
                    pair = [m, w]
                    m.engage(w)
                    #Verify that the new pair doesn't create instability
                    if self.__temp.is_stable(pair):
                        self.__temp.push(pair)
                        self.match()
                        self.__temp.pop()
                    m.break_up()
            # Get the man back in the stack
            self.men.append(m)
        else:
            if self.solution is None:
                self.solution = self.__temp.toString()
